#include <linux/err.h>
#include <linux/errno.h>
#include <linux/types.h>
#include <linux/dcache.h>
#include <linux/fs2.h>
#include <linux/gfp.h>
#include <linux/fs_struct.h>
#include <linux/sched.h>
#include <linux/cache.h>
#include <linux/hash.h>
#include <linux/rculist.h>
#include <linux/stat.h>

#include <asm/thread_info.h>
#include <asm/atomic.h>

#define D_HASHBITS     d_hash_shift
#define D_HASHMASK     d_hash_mask

static unsigned int d_hash_mask;
static unsigned int d_hash_shift;
static struct hlist_head *dentry_hashtable;

static inline struct hlist_head *d_hash(struct dentry *parent,
					unsigned long hash)
{
	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
	return dentry_hashtable + (hash & D_HASHMASK);
}

static void __d_rehash(struct dentry * entry, struct hlist_head *list)
{
 	entry->d_flags &= ~DCACHE_UNHASHED;
 	hlist_add_head_rcu(&entry->d_hash, list);
}

static void _d_rehash(struct dentry * entry)
{
	__d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash));
}

void d_rehash(struct dentry * entry)
{
	// spin_lock(&dcache_lock);
	// spin_lock(&entry->d_lock);
	_d_rehash(entry);
	// spin_unlock(&entry->d_lock);
	// spin_unlock(&dcache_lock);
}

struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
{
	unsigned int len = name->len;
	unsigned int hash = name->hash;
	const unsigned char *str = name->name;
	struct hlist_head *head = d_hash(parent,hash);
	struct dentry *found = NULL;
	struct hlist_node *node;
	struct dentry *dentry;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	// rcu_read_lock();

	hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		struct qstr *qstr;

		if (dentry->d_name.hash != hash)
			continue;
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		if (dentry->d_parent != parent)
			continue;
		printf("this is %s(): %d\r\n", __func__, __LINE__);

		// spin_lock(&dentry->d_lock);

		/*
		 * Recheck the dentry after taking the lock - d_move may have
		 * changed things.  Don't bother checking the hash because we're
		 * about to compare the whole name anyway.
		 */
		if (dentry->d_parent != parent)
			goto next;
		printf("this is %s(): %d\r\n", __func__, __LINE__);

		/* non-existing due to RCU? */
		if (d_unhashed(dentry))
			goto next;
		printf("this is %s(): %d\r\n", __func__, __LINE__);

		/*
		 * It is safe to compare names since d_move() cannot
		 * change the qstr (protected by d_lock).
		 */
		qstr = &dentry->d_name;
		if (parent->d_op && parent->d_op->d_compare) {
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			if (parent->d_op->d_compare(parent, qstr, name))
				goto next;
		} else {
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			if (qstr->len != len)
				goto next;
			if (memcmp(qstr->name, str, len))
				goto next;
			printf("this is %s(): %d\r\n", __func__, __LINE__);
		}

		printf("this is %s(): %d\r\n", __func__, __LINE__);
		atomic_inc(&dentry->d_count);
		found = dentry;
		// spin_unlock(&dentry->d_lock);
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		break;
next:
		// spin_unlock(&dentry->d_lock);
		printf("this is %s(): %d\r\n", __func__, __LINE__);
 	}
 	// rcu_read_unlock();

	printf("this is %s(): %d\r\n", __func__, __LINE__);
 	return found;
}

struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
{
	struct dentry * dentry = NULL;
	unsigned long seq;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

    // do {
		// seq = read_seqbegin(&rename_lock);
		dentry = __d_lookup(parent, name);
		// if (dentry)
		// break;
	// } while (read_seqretry(&rename_lock, seq));
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	return dentry;
}

static void __d_instantiate(struct dentry *dentry, struct inode *inode)
{
	if (inode)
		list_add(&dentry->d_alias, &inode->i_dentry);
	dentry->d_inode = inode;
	// fsnotify_d_instantiate(dentry, inode);
}

void d_instantiate(struct dentry *entry, struct inode *inode)
{
	// BUG_ON(!list_empty(&entry->d_alias));
	// spin_lock(&dcache_lock);
	__d_instantiate(entry, inode);
	// spin_unlock(&dcache_lock);
	// security_d_instantiate(entry, inode);
}

static void switch_names(struct dentry *dentry, struct dentry *target)
{
	if (dname_external(target)) {
		if (dname_external(dentry)) {
			/*
			 * Both external: swap the pointers
			 */
			swap(target->d_name.name, dentry->d_name.name);
		} else {
			/*
			 * dentry:internal, target:external.  Steal target's
			 * storage and make target internal.
			 */
			memcpy(target->d_iname, dentry->d_name.name,
					dentry->d_name.len + 1);
			dentry->d_name.name = target->d_name.name;
			target->d_name.name = target->d_iname;
		}
	} else {
		if (dname_external(dentry)) {
			/*
			 * dentry:external, target:internal.  Give dentry's
			 * storage to target and make dentry internal
			 */
			memcpy(dentry->d_iname, target->d_name.name,
					target->d_name.len + 1);
			target->d_name.name = dentry->d_name.name;
			dentry->d_name.name = dentry->d_iname;
		} else {
			/*
			 * Both are internal.  Just copy target to dentry
			 */
			memcpy(dentry->d_iname, target->d_name.name,
					target->d_name.len + 1);
			dentry->d_name.len = target->d_name.len;
			return;
		}
	}
	swap(dentry->d_name.len, target->d_name.len);
}

static void d_move_locked(struct dentry * dentry, struct dentry * target)
{
	struct hlist_head *list;

	if (!dentry->d_inode)
		printf("VFS: moving negative dcache entry\r\n");

	// write_seqlock(&rename_lock);
	/*
	 * XXXX: do we really need to take target->d_lock?
	 */
	// if (target < dentry) {
	// 	spin_lock(&target->d_lock);
	// 	spin_lock_nested(&dentry->d_lock, DENTRY_D_LOCK_NESTED);
	// } else {
	// 	spin_lock(&dentry->d_lock);
	// 	spin_lock_nested(&target->d_lock, DENTRY_D_LOCK_NESTED);
	// }

	/* Move the dentry to the target hash queue, if on different bucket */
	if (d_unhashed(dentry))
		goto already_unhashed;

	hlist_del_rcu(&dentry->d_hash);

already_unhashed:
	list = d_hash(target->d_parent, target->d_name.hash);
	__d_rehash(dentry, list);

	/* Unhash the target: dput() will then get rid of it */
	__d_drop(target);

	list_del(&dentry->d_u.d_child);
	list_del(&target->d_u.d_child);

	/* Switch the names.. */
	switch_names(dentry, target);
	swap(dentry->d_name.hash, target->d_name.hash);

	/* ... and switch the parents */
	if (IS_ROOT(dentry)) {
		dentry->d_parent = target->d_parent;
		target->d_parent = target;
		INIT_LIST_HEAD(&target->d_u.d_child);
	} else {
		swap(dentry->d_parent, target->d_parent);

		/* And add them back to the (new) parent lists */
		list_add(&target->d_u.d_child, &target->d_parent->d_subdirs);
	}

	list_add(&dentry->d_u.d_child, &dentry->d_parent->d_subdirs);
	// spin_unlock(&target->d_lock);
	// fsnotify_d_move(dentry);
	// spin_unlock(&dentry->d_lock);
	// write_sequnlock(&rename_lock);
}

void d_move(struct dentry * dentry, struct dentry * target)
{
	// spin_lock(&dcache_lock);
	d_move_locked(dentry, target);
	// spin_unlock(&dcache_lock);
}

static struct dentry * __d_find_alias(struct inode *inode, int want_discon)
{
	struct list_head *head, *next, *tmp;
	struct dentry *alias, *discon_alias=NULL;

	head = &inode->i_dentry;
	next = inode->i_dentry.next;
	while (next != head) {
		tmp = next;
		next = tmp->next;
		prefetch(next);
		alias = list_entry(tmp, struct dentry, d_alias);
 		if (S_ISDIR(inode->i_mode) || !d_unhashed(alias)) {
			if (IS_ROOT(alias) &&
			    (alias->d_flags & DCACHE_DISCONNECTED))
				discon_alias = alias;
			else if (!want_discon) {
				// __dget_locked(alias);
				return alias;
			}
		}
	}
	// if (discon_alias)
		// __dget_locked(discon_alias);
	return discon_alias;
}

struct dentry *d_splice_alias(struct inode *inode, struct dentry *dentry)
{
	struct dentry *new = NULL;

	if (inode && S_ISDIR(inode->i_mode)) {
		// spin_lock(&dcache_lock);
		new = __d_find_alias(inode, 1);
		if (new) {
			// BUG_ON(!(new->d_flags & DCACHE_DISCONNECTED));
			// spin_unlock(&dcache_lock);
			// security_d_instantiate(new, inode);
			d_rehash(dentry);
			d_move(new, dentry);
			// iput(inode);
		} else {
			/* already taking dcache_lock, so d_add() by hand */
			__d_instantiate(dentry, inode);
			// spin_unlock(&dcache_lock);
			// security_d_instantiate(dentry, inode);
			d_rehash(dentry);
		}
	} else
		d_add(dentry, inode);
	return new;
}

struct dentry *d_alloc(struct dentry * parent, const struct qstr *name)
{
	struct dentry *dentry;
	char *dname;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	// dentry = kmem_cache_alloc(dentry_cache, GFP_KERNEL);
    dentry = (struct dentry *)kmalloc(sizeof(struct dentry));
	if (!dentry)
		return NULL;

	// if (name->len > DNAME_INLINE_LEN-1) {
	// 	dname = kmalloc(name->len + 1, GFP_KERNEL);
	// 	if (!dname) {
	// 		kmem_cache_free(dentry_cache, dentry); 
	// 		return NULL;
	// 	}
	// } else  {
		dname = dentry->d_iname;
	// }	
	dentry->d_name.name = dname;

	dentry->d_name.len = name->len;
	dentry->d_name.hash = name->hash;
	memcpy(dname, name->name, name->len);
	dname[name->len] = 0;

	atomic_set(&dentry->d_count, 1);
	dentry->d_flags = DCACHE_UNHASHED;
	// spin_lock_init(&dentry->d_lock);
	dentry->d_inode = NULL;
	dentry->d_parent = NULL;
	dentry->d_sb = NULL;
	dentry->d_op = NULL;
	dentry->d_fsdata = NULL;
	dentry->d_mounted = 0;
	INIT_HLIST_NODE(&dentry->d_hash);
	INIT_LIST_HEAD(&dentry->d_lru);
	INIT_LIST_HEAD(&dentry->d_subdirs);
	INIT_LIST_HEAD(&dentry->d_alias);

	if (parent) {
		dentry->d_parent = dget(parent);
		dentry->d_sb = parent->d_sb;
	} else {
		INIT_LIST_HEAD(&dentry->d_u.d_child);
	}

	// spin_lock(&dcache_lock);
	if (parent)
		list_add(&dentry->d_u.d_child, &parent->d_subdirs);
	// dentry_stat.nr_dentry++;
	// spin_unlock(&dcache_lock);

	printf("this is %s(): %d\r\n", __func__, __LINE__);
	return dentry;
}

struct dentry *d_alloc_root(struct inode *root_inode)
{
	struct dentry *res = NULL;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	if (root_inode) {
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		static const struct qstr name = { .name = "/", .len = 1 };

		res = d_alloc(NULL, &name);
		if (res) {
			res->d_sb = root_inode->i_sb;
			res->d_parent = res;
			d_instantiate(res, root_inode);
		}
	}
	return res;
}

static int prepend(char **buffer, int *buflen, const char *str, int namelen)
{
	*buflen -= namelen;
	if (*buflen < 0)
		return -ENAMETOOLONG;
	*buffer -= namelen;
	memcpy(*buffer, str, namelen);
	return 0;
}

static int prepend_name(char **buffer, int *buflen, struct qstr *name)
{
	return prepend(buffer, buflen, name->name, name->len);
}

char *__d_path(const struct path *path, struct path *root,
	       char *buffer, int buflen)
{
	struct dentry *dentry = path->dentry;
	struct vfsmount *vfsmnt = path->mnt;
	char *end = buffer + buflen;
	char *retval;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	printf("this is %s(): %d >>> vfsmnt->mnt_sb->s_type->name = %s\r\n", __func__, __LINE__, vfsmnt->mnt_sb->s_type->name);
	printf("this is %s(): %d >>> vfsmnt->mnt_parent->mnt_sb->s_type->name = %s\r\n", __func__, __LINE__, vfsmnt->mnt_parent->mnt_sb->s_type->name);

	// spin_lock(&vfsmount_lock);
	prepend(&end, &buflen, "\0", 1);
	// if (d_unlinked(dentry) &&
	// 	(prepend(&end, &buflen, " (deleted)", 10) != 0))
	// 		goto Elong;

	if (buflen < 1)
		goto Elong;
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	/* Get '/' right */
	retval = end-1;
	*retval = '/';
	printf("this is %s(): %d\r\n", __func__, __LINE__);

	for (;;) {
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		struct dentry * parent;

		if (dentry == root->dentry && vfsmnt == root->mnt)
			break;
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		if (dentry == vfsmnt->mnt_root || IS_ROOT(dentry)) {
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			/* Global root? */
			if (vfsmnt->mnt_parent == vfsmnt) {
				printf("this is %s(): %d\r\n", __func__, __LINE__);
				goto global_root;
			}
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			dentry = vfsmnt->mnt_mountpoint;
			vfsmnt = vfsmnt->mnt_parent;
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			continue;
		}
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		parent = dentry->d_parent;
		prefetch(parent);
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		if ((prepend_name(&end, &buflen, &dentry->d_name) != 0) ||
		    (prepend(&end, &buflen, "/", 1) != 0))
			goto Elong;
		printf("this is %s(): %d\r\n", __func__, __LINE__);
		retval = end;
		dentry = parent;
	}

out:
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	// spin_unlock(&vfsmount_lock);
	return retval;

global_root:
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	retval += 1;	/* hit the slash */
	if (prepend_name(&retval, &buflen, &dentry->d_name) != 0)
		goto Elong;
	root->mnt = vfsmnt;
	root->dentry = dentry;
	goto out;

Elong:
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	retval = ERR_PTR(-ENAMETOOLONG);
	goto out;
}

long sys_getcwd(char *buf, unsigned long size)
{
	int error;
	struct path pwd, root;
	// char *page = (char *) __get_free_page(GFP_USER);
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	char *page = (char *) __get_free_pages(GFP_USER, 1);

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	if (!page)
		return -ENOMEM;

	printf("this is %s(): %d\r\n", __func__, __LINE__);
	// read_lock(&current->fs->lock);
	pwd = current->fs->pwd;
	// path_get(&pwd);
	root = current->fs->root;
	// path_get(&root);
	// read_unlock(&current->fs->lock);

	error = -ENOENT;
	// spin_lock(&dcache_lock);
	// if (!d_unlinked(pwd.dentry)) {
		unsigned long len;
		struct path tmp = root;
		char * cwd;

		cwd = __d_path(&pwd, &tmp, page, PAGE_SIZE);
		// spin_unlock(&dcache_lock);

		error = PTR_ERR(cwd);
		if (IS_ERR(cwd))
			goto out;

		error = -ERANGE;
		len = PAGE_SIZE + page - cwd;
		if (len <= size) {
			printf("this is %s(): %d\r\n", __func__, __LINE__);
			error = len;
			// if (copy_to_user(buf, cwd, len))
			if (memcpy(buf, cwd, len))
				error = -EFAULT;
		}
	// } else {
		// spin_unlock(&dcache_lock);
	// }

out:
	// path_put(&pwd);
	// path_put(&root);
	// free_page((unsigned long) page);
	printf("this is %s(): %d\r\n", __func__, __LINE__);
	return error;
}

static unsigned long dhash_entries = 65536;

static void dcache_init(void)
{
	int loop;

	/* 
	 * A constructor could be added for stable state like the lists,
	 * but it is probably not worth it because of the cache nature
	 * of the dcache. 
	 */
	// dentry_cache = KMEM_CACHE(dentry,
	// 	SLAB_RECLAIM_ACCOUNT|SLAB_PANIC|SLAB_MEM_SPREAD);
	
	// register_shrinker(&dcache_shrinker);

	/* Hash may have been set up in dcache_init_early */
	// if (!hashdist)
		// return;

	dentry_hashtable =
		alloc_large_system_hash("Dentry cache",
					sizeof(struct hlist_head),
					dhash_entries,
					13,
					0,
					&d_hash_shift,
					&d_hash_mask,
					0);

	for (loop = 0; loop < (1 << d_hash_shift); loop++)
		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
}

void vfs_caches_init(unsigned long mempages)
{
	// unsigned long reserve;

	printf("this is %s(): %d\r\n", __func__, __LINE__);

	// /* Base hash sizes on available memory, with a reserve equal to
    //        150% of current kernel size */

	// reserve = min((mempages - nr_free_pages()) * 3/2, mempages - 1);
	// mempages -= reserve;

	// names_cachep = kmem_cache_create("names_cache", PATH_MAX, 0,
	// 		SLAB_HWCACHE_ALIGN|SLAB_PANIC, NULL);

	dcache_init();
	inode_init();
	// files_init(mempages);
	mnt_init();
	// bdev_cache_init();
	// chrdev_init();
}
